package com.linzm.leetcode.primary.exercises3_20230122;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author zimingl
 * @Date 2023/1/23 21:51
 * @Description: 完成一半题目
 */
public class Demo9 {
    /**
     * 输入：questions = [1,5,1,3,4,5,2,5,3,3,8,6]
     * 输出：2
     * 解释：有 6 位扣友在 12 道题目中选择题目，需要选择 6 题。
     * 选择完成知识点类型为 3、5 的题目，因此至少包含 2 种知识点类型。
     */
    public static void main(String[] args) {
        Demo9 demo9 = new Demo9();
        int[] questions = {1, 5, 1, 3, 4, 5, 2, 5, 3, 3, 8, 6};
        int halfQuestions = demo9.halfQuestions2(questions);
        System.out.println(halfQuestions);
    }

    private int halfQuestions(int[] questions) {
        int n = questions.length / 2;
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < questions.length; i++) {
            treeMap.put(questions[i], treeMap.getOrDefault(questions[i], 0) + 1);
        }
        List<Integer> collect = treeMap.entrySet().stream()
                .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                .map(Map.Entry::getValue).collect(Collectors.toList());
        int[] ints = collect.stream().mapToInt(x -> x).toArray();
        int count = 0;
        for (int i = 0; i < ints.length; i++) {
            while (n > 0 && ints[i] > 0) {
                ints[i]--;
                n--;
            }
            count++;
            if (n <= 0) {
                break;
            }
        }
        return count;
    }

    private int halfQuestions2(int[] questions) {
        int n = questions.length, np = n / 2, res = 1, idx = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        Arrays.stream(questions).forEach(q -> map.merge(q, -1, Integer::sum));
        List<Integer> sortedValues = map.values().stream()
                .sorted(Integer::compareTo).collect(Collectors.toList());
        while ((np += sortedValues.get(idx++)) > 0) res++;
        return res;
    }
}
